package com.sort;

public class MergeSort {
    public void sort(int[] arr,int low,int high){
        int mid = (high+low)/2;
        if(low<high){
            sort(arr,low,mid);
            sort(arr,mid+1,high);
            //左右归并
            merge(arr,low,mid,high);
        }
    }
    public void merge(int[] arr,int low,int mid,int high){
        int[] tmp = new int[high-low+1];
        int i=low, j=mid+1, k=0;
        //把较小的数先移到新数组中
        while (i<=mid && j<=high){
            if(arr[i]<arr[j]){
                tmp[k++] = arr[i++];
            }else{
                tmp[k++] = arr[j++];
            }
        }
        //把左边剩余的数移入数组
        while (i<=mid){
            tmp[k++] = arr[i++];
        }
        //把右边剩余的数移入数组
        while (j<=high){
            tmp[k++] = arr[j++];
        }
        //把新数组中的数覆盖arr数组
        for(int x=0;x<tmp.length;x++){
            arr[x+low] = tmp[x];
        }
    }
}
